{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of Beautiful Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautifulSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计美丽子数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组<code>nums</code>&nbsp;。每次操作中，你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择两个满足&nbsp;<code>0 &lt;= i, j &lt; nums.length</code>&nbsp;的不同下标&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code>&nbsp;。</li>\n",
    "\t<li>选择一个非负整数&nbsp;<code>k</code>&nbsp;，满足 <code>nums[i]</code>&nbsp;和 <code>nums[j]</code>&nbsp;在二进制下的第 <code>k</code>&nbsp;位（下标编号从 <strong>0</strong>&nbsp;开始）是 <code>1</code>&nbsp;。</li>\n",
    "\t<li>将 <code>nums[i]</code>&nbsp;和 <code>nums[j]</code>&nbsp;都减去&nbsp;<code>2<sup>k</sup></code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 <code>0</code>&nbsp;的数组，那么我们称它是一个 <strong>美丽</strong>&nbsp;的子数组。</p>\n",
    "\n",
    "<p>请你返回数组 <code>nums</code>&nbsp;中 <strong>美丽子数组</strong>&nbsp;的数目。</p>\n",
    "\n",
    "<p>子数组是一个数组中一段连续 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,3,1,2,4]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>nums 中有 2 个美丽子数组：[4,<em><strong>3,1,2</strong></em>,4] 和 [<em><strong>4,3,1,2,4</strong></em>] 。\n",
    "- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：\n",
    "  - 选择 [<em><strong>3</strong></em>, 1, <em><strong>2</strong></em>] 和 k = 1 。将 2 个数字都减去 2<sup>1</sup> ，子数组变成 [1, 1, 0] 。\n",
    "  - 选择 [<em><strong>1</strong></em>, <em><strong>1</strong></em>, 0] 和 k = 0 。将 2 个数字都减去 2<sup>0</sup> ，子数组变成 [0, 0, 0] 。\n",
    "- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：\n",
    "  - 选择 [<em><strong>4</strong></em>, 3, 1, 2, <em><strong>4</strong></em>] 和 k = 2 。将 2 个数字都减去 2<sup>2</sup> ，子数组变成 [0, 3, 1, 2, 0] 。\n",
    "  - 选择 [0, <em><strong>3</strong></em>, <em><strong>1</strong></em>, 2, 0] 和 k = 0 。将 2 个数字都减去 2<sup>0</sup> ，子数组变成 [0, 2, 0, 2, 0] 。\n",
    "  - 选择 [0, <em><strong>2</strong></em>, 0, <em><strong>2</strong></em>, 0] 和 k = 1 。将 2 个数字都减去 2<sup>1</sup> ，子数组变成 [0, 0, 0, 0, 0] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,10,4]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>nums 中没有任何美丽子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-beautiful-subarrays](https://leetcode.cn/problems/count-the-number-of-beautiful-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-beautiful-subarrays](https://leetcode.cn/problems/count-the-number-of-beautiful-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,1,2,4]', '[1,10,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1 if nums[0] == 0 else 0\n",
    "\n",
    "        res = 0\n",
    "        cnt = dict()\n",
    "        prefix = 0 \n",
    "\n",
    "        for i in range(n):\n",
    "            cur = prefix ^ nums[i]\n",
    "            if cur == 0:\n",
    "                res += 1\n",
    "            \n",
    "            if cur not in cnt:\n",
    "                cnt[cur] = 0\n",
    "            res += cnt[cur]\n",
    "            cnt[cur] += 1\n",
    "            prefix = cur\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ls = len(nums)\n",
    "        # p[i] = nums[:i]的异或结果\n",
    "        p = nums\n",
    "        for i in range(1, ls):\n",
    "            p[i] ^= p[i-1]\n",
    "        \n",
    "        ans = 0\n",
    "        # d[x] = 之前异或结果为x的p数量\n",
    "        d = defaultdict(int)\n",
    "        d[0] += 1\n",
    "        for x in p:\n",
    "            ans += d[x]\n",
    "            d[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        d=defaultdict(int)\n",
    "        arr=[0]\n",
    "        ans=0\n",
    "        d[0]=1\n",
    "        for i in range(n):\n",
    "            x=nums[i]^arr[-1]\n",
    "            arr.append(x)\n",
    "            d[x]+=1\n",
    "        for p in d:\n",
    "            m=d[p]\n",
    "            ans+=m*(m-1)//2\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        d=defaultdict(int)\n",
    "        arr=[0]\n",
    "        ans=0\n",
    "        d[0]=1\n",
    "        for i in range(n):\n",
    "            x=nums[i]^arr[-1]\n",
    "            arr.append(x)\n",
    "            d[x]+=1\n",
    "        for p in d:\n",
    "            m=d[p]\n",
    "            ans+=m*(m-1)//2\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1 if nums[0]==0 else 0\n",
    "        res = nums[0]\n",
    "        res_dict = collections.defaultdict(int)\n",
    "        res_dict[res] = 1\n",
    "        ans = 1 if res == 0 else 0\n",
    "        for v in nums[1:]:\n",
    "            res ^= v\n",
    "            if res in res_dict:\n",
    "                ans += res_dict[res]\n",
    "            res_dict[res] += 1\n",
    "            if res == 0:\n",
    "                ans += 1\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        pre = [0] * (n + 1)\n",
    "        pre[0] = 0\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] ^ nums[i]\n",
    "        cnt = Counter()\n",
    "        for p in pre:            \n",
    "            ans += cnt[p]\n",
    "            cnt[p] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, xor, initial=0))\n",
    "        ans, cnt = 0, Counter()\n",
    "        for x in s:\n",
    "            # 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了\n",
    "            ans += cnt[x]\n",
    "            cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "            n = len(nums)\n",
    "            pre = list(accumulate(nums, xor, initial = 0))\n",
    "            cnt = Counter()\n",
    "            for x in pre:\n",
    "                cnt[x] += 1\n",
    "            res = 0\n",
    "            for val in cnt.values():\n",
    "                res += val * (val - 1) // 2\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s=list(accumulate(nums,xor,initial=0))\n",
    "        ans=0\n",
    "        cnt=Counter()\n",
    "        for x in s:\n",
    "            ans+=cnt[x]\n",
    "            cnt[x]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        return sum(v * (v - 1) >> 1 for v in Counter(accumulate(nums, xor, initial = 0)).values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # PrefixXORsum = [0]\n",
    "        # result = 0\n",
    "        # for num in nums:\n",
    "        #     result ^= num\n",
    "        #     PrefixXORsum.append(result)\n",
    "        # PrefixXORsum = accumulate(nums, xor, initial = 0)\n",
    "        # count = Counter()\n",
    "        # ans = 0\n",
    "        # for XORsum in PrefixXORsum:\n",
    "        #     ans += count[XORsum]\n",
    "        #     count[XORsum] += 1\n",
    "        ans = s = 0\n",
    "        count = Counter({s:1})\n",
    "        for num in nums:\n",
    "            s ^= num\n",
    "            ans += count[s]\n",
    "            count[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        sum, ans = 0, 0\n",
    "        mp[0] = 1\n",
    "        for i, ai in enumerate(nums):\n",
    "            sum ^= ai\n",
    "            ans += mp[sum]\n",
    "            mp[sum] += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # PrefixXORsum = [0]\n",
    "        # result = 0\n",
    "        # for num in nums:\n",
    "        #     result ^= num\n",
    "        #     PrefixXORsum.append(result)\n",
    "        PrefixXORsum = accumulate(nums, xor, initial = 0)\n",
    "        count = Counter()\n",
    "        ans = 0\n",
    "        for XORsum in PrefixXORsum:\n",
    "            ans += count[XORsum]\n",
    "            count[XORsum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s=list(accumulate(nums,xor,initial=0))\n",
    "        ans=0\n",
    "        cnt=Counter()\n",
    "        for x in s:\n",
    "            ans += cnt[x]\n",
    "            cnt[x] += 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mapping = {0:1}\n",
    "        xor = 0\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            xor = xor ^ num\n",
    "            if(xor in mapping):\n",
    "                result += mapping[xor]\n",
    "                mapping[xor] += 1\n",
    "            else:\n",
    "                mapping[xor] = 1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ns = list(accumulate(nums, xor, initial=0))\n",
    "        ans, cnt = 0, Counter()\n",
    "        for x in ns:\n",
    "            ans += cnt[x]\n",
    "            cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # PrefixXORsum = [0]\n",
    "        # result = 0\n",
    "        # for num in nums:\n",
    "        #     result ^= num\n",
    "        #     PrefixXORsum.append(result)\n",
    "        # PrefixXORsum = accumulate(nums, xor, initial = 0)\n",
    "        # count = Counter()\n",
    "        # ans = 0\n",
    "        # for XORsum in PrefixXORsum:\n",
    "        #     ans += count[XORsum]\n",
    "        #     count[XORsum] += 1\n",
    "        ans = s = 0\n",
    "        count = Counter({s:1})\n",
    "        for num in nums:\n",
    "            s ^= num\n",
    "            ans += count[s]\n",
    "            count[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ans, cur = 0, 0\n",
    "        pre = Counter()\n",
    "        pre[0] = 1\n",
    "        for i in nums:\n",
    "            nxt = cur ^ i\n",
    "            if nxt in pre: ans += pre[nxt]\n",
    "            cur = nxt\n",
    "            pre[cur] += 1\n",
    "        return ans\n",
    "                        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, initial=0, func=operator.xor))\n",
    "        ans = 0\n",
    "        s_dict = Counter()\n",
    "        for v in s:\n",
    "            ans += s_dict[v]\n",
    "            s_dict[v] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        count = Counter({s:1})\n",
    "        for num in nums:\n",
    "            s ^= num\n",
    "            ans += count[s]\n",
    "            count[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        3 1 2\n",
    "        11 \n",
    "        01\n",
    "        10\n",
    "        \n",
    "        4 3 1 2 4\n",
    "        011\n",
    "        001\n",
    "        010\n",
    "        100\n",
    "        100\n",
    "        异或为 0\n",
    "        \n",
    "        定义前缀异或\n",
    "        f[4] = 0 ^ a1 ^ a2 ^ a3 ^ a4 \n",
    "        f[1] = a1 ^ 0\n",
    "        f[2...4] = f[4] ^ f1\n",
    "        \n",
    "        f[j] ^ f[i] = 0\n",
    "        f[j] ^ f[i] ^ f[i] = f[j] = f[i]\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            f[i + 1] = f[i] ^ nums[i]\n",
    "        ans = 0\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = 1\n",
    "        for i in range(n):\n",
    "            if f[i + 1] in mp:\n",
    "                ans += mp[f[i + 1]]\n",
    "            mp[f[i + 1]] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        now=0\n",
    "        c=collections.Counter()\n",
    "        c[now]+=1\n",
    "        for n in nums:\n",
    "            now^=n\n",
    "            ans+=c[now]\n",
    "            c[now]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # 异或和为0的子数组\n",
    "        # 前缀异或和为0或相等的搭配\n",
    "        c = Counter(accumulate(nums, xor, initial = 0))\n",
    "        return sum(comb(v, 2) for k, v in c.items() if v > 1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    美丽子数组\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums,xor,initial= 0))\n",
    "        ans,cnt= 0,Counter()\n",
    "        for x in s:\n",
    "            ans +=cnt[x]\n",
    "            cnt[x] +=1\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        total=0\n",
    "        hashmap=Counter()\n",
    "        hashmap[0]=1\n",
    "        res=0\n",
    "        for x in nums:\n",
    "            total^=x \n",
    "            res+=hashmap[total]\n",
    "            hashmap[total]+=1\n",
    "        return res \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        #前缀异或和+哈希表记录\n",
    "        '''\n",
    "        cnt=Counter({0:1})\n",
    "        #注意自己不能异或自己\n",
    "        ans=0\n",
    "        pre=0\n",
    "        for x in nums:\n",
    "            pre^=x  \n",
    "            ans+=cnt[pre]\n",
    "            cnt[pre]+=1\n",
    "        return ans\n",
    "        '''\n",
    "        s=list(accumulate(nums,xor,initial=0))\n",
    "        ans,cnt=0,Counter()\n",
    "        for x in s:\n",
    "            ans+=cnt[x]\n",
    "            cnt[x]+=1\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    美丽子数组\n",
    "    奇偶性操作多考虑  异或操作\n",
    "    前缀和 {\n",
    "        前缀与和  前缀异或和  前缀和  前缀乘积\n",
    " }\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums,xor,initial= 0))\n",
    "        ans,cnt= 0,Counter()\n",
    "        for x in s:\n",
    "            ans +=cnt[x]\n",
    "            cnt[x] +=1\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        xorAccu = Counter(chain([0], accumulate(nums, xor)))\n",
    "        res = 0\n",
    "        for k, v in xorAccu.items():\n",
    "            if v > 1:\n",
    "                res += v*(v-1)//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: [int]) -> int:\n",
    "        dc=defaultdict(int)\n",
    "        dc[0]=1\n",
    "        tot=0\n",
    "        pre=0\n",
    "        for i in range(len(nums)):\n",
    "            pre=pre^nums[i]\n",
    "            tot=tot+dc[pre]\n",
    "            dc[pre]+=1\n",
    "        return tot\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_sum = 0\n",
    "        count = {0:1}\n",
    "        for num in nums:\n",
    "            pre_sum = pre_sum^num\n",
    "            if pre_sum not in count:\n",
    "                count[pre_sum]=1\n",
    "            else:\n",
    "                res += count[pre_sum]\n",
    "                count[pre_sum]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        d = {0: 1}\n",
    "        xor = 0\n",
    "        for x in nums:\n",
    "            xor ^= x\n",
    "            if xor in d:\n",
    "                d[xor] += 1\n",
    "            else:\n",
    "                d[xor] = 1\n",
    "        res = 0\n",
    "        for _, v in d.items():\n",
    "            res += v * (v - 1) // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        mp = collections.defaultdict(int)\n",
    "        mp[0] = 1\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            pre ^= n\n",
    "            ans += mp.get(pre, 0)\n",
    "            mp[pre] += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        lst = [0] + [0 for _ in nums]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            lst[i] = lst[i-1]^nums[i-1]\n",
    "        sums = 0\n",
    "        for v in Counter(lst).values():\n",
    "            sums += v * (v-1) >> 1\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, xor, initial=0))\n",
    "        ans, cnt = 0, Counter()\n",
    "\n",
    "        # i 到 j 的异或和可以看作是“前缀异或数组”的 s[j + 1] ^ s[i]\n",
    "        # 所以 i = j 就意味着 i ^ j = 0，即子数组中全部的位为偶数\n",
    "\n",
    "        for x in s:\n",
    "            # 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了\n",
    "            ans += cnt[x]\n",
    "            cnt[x] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # 异或和为0的子数组\n",
    "        # 前缀异或和为0或相等的搭配\n",
    "        c = Counter(accumulate(nums, xor, initial = 0))\n",
    "        return sum(comb(v, 2) for v in c.values())\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1 if nums[0]==0 else 0\n",
    "        res = nums[0]\n",
    "        # 前缀异或值\n",
    "        res_dict = collections.defaultdict(int)\n",
    "        res_dict[res] = 1\n",
    "        ans = 1 if res == 0 else 0 # 0 的时候 就有一个美丽子数组 【0】\n",
    "        for v in nums[1:]:\n",
    "            res ^= v\n",
    "            # 之前有没有异或值为 res的 有的话意味着 当前-res_dict[res]对应的位置是美丽的\n",
    "            if res in res_dict:\n",
    "                ans += res_dict[res]\n",
    "            res_dict[res] += 1\n",
    "            # 记录值为res的次数\n",
    "            if res == 0:\n",
    "                ans += 1\n",
    "                # 如果res == 0 意味着 【：res】是美丽的\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s = [0]\n",
    "        for x in nums:\n",
    "            s.append(s[-1] ^ x)\n",
    "        cnt = Counter()\n",
    "        res = 0\n",
    "        for x in s:\n",
    "            res += cnt[x]\n",
    "            cnt[x] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mapping = {0:1}\n",
    "        xor = 0\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            xor = xor ^ num\n",
    "            if(xor in mapping):\n",
    "                result += mapping[xor]\n",
    "                mapping[xor] += 1\n",
    "            else:\n",
    "                mapping[xor] = 1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        cnt = Counter({s: 1})  # s[0]\n",
    "        for x in nums:\n",
    "            s ^= x\n",
    "            ans += cnt[s]\n",
    "            cnt[s] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        cnt = Counter({s: 1})  # s[0]\n",
    "        for x in nums:\n",
    "            s ^= x\n",
    "            ans += cnt[s]\n",
    "            cnt[s] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # 异或和为0的子数组\n",
    "        # 前缀异或和为0或相等的搭配\n",
    "        c = Counter(accumulate(nums, xor, initial = 0))\n",
    "        return sum(comb(v, 2) for v in c.values() if v > 1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        cnt = Counter({s:1})\n",
    "        for x in nums:\n",
    "            s ^= x\n",
    "            ans += cnt[s]\n",
    "            cnt[s] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        s = list(accumulate(nums, xor, initial=0))\n",
    "        ans, cnt = 0, Counter()\n",
    "\n",
    "        # i 到 j 的异或和可以看作是“前缀异或数组”的 s[j + 1] ^ s[i]\n",
    "        # 所以 i = j 就意味着 i ^ j = 0，即子数组中全部的位为偶数\n",
    "\n",
    "        for x in s:\n",
    "            # 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了\n",
    "            ans += cnt[x]\n",
    "            cnt[x] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums) \n",
    "        pre = [0] * (n + 1) \n",
    "        for i in range(1, n + 1) : \n",
    "            pre[i] = pre[i - 1] ^ nums[i - 1] \n",
    "        print(pre)\n",
    "        h = defaultdict(int) \n",
    "        res = 0 \n",
    "        for i in range(n + 1) : \n",
    "            res += h[pre[i]] \n",
    "            h[pre[i]] += 1 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = {0: 1}\n",
    "        xor = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            xor ^= nums[i]\n",
    "            if xor in prefix.keys():\n",
    "                res += prefix[xor]\n",
    "            prefix[xor] = prefix.get(xor, 0) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # 异或和为0的子数组\n",
    "        # 前缀异或和为0或相等的搭配\n",
    "        c = Counter(accumulate(nums, xor, initial = 0))\n",
    "        return sum(comb(v, 2) for k, v in c.items())\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "            n = len(nums)\n",
    "            pre = [0] * (n + 1)\n",
    "            m = {}\n",
    "            m[0] = 1\n",
    "            for i in range(n):\n",
    "                pre[i + 1] = pre[i] ^ nums[i]\n",
    "                m[pre[i + 1]] = m.get(pre[i + 1], 0) + 1\n",
    "            res = 0\n",
    "            for val in m.values():\n",
    "                res += val * (val - 1) // 2\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        lst = [0] + [0 for _ in nums]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            lst[i] = lst[i-1]^nums[i-1]\n",
    "        sums = 0\n",
    "        for v in Counter(lst).values():\n",
    "            sums += sum([x for x in range(v)])\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        # 异或和为0的子数组\n",
    "        # 前缀异或和为0或相等的搭配\n",
    "        c = Counter(accumulate(nums, xor, initial = 0))\n",
    "        return sum(comb(v, 2) for v in c.values() if v > 1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef beautifulSubarrays(self, nums):\n",
    "\t\tcnt = {0: 1}\n",
    "\t\tcur = 0\n",
    "\t\tfor num in nums:\n",
    "\t\t\tcur ^= num\n",
    "\t\t\tcnt[cur] = cnt.get(cur, 0) + 1\n",
    "\t\treturn sum([x * (x - 1) // 2 for x in cnt.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulSubarrays(self, nums: List[int]) -> int:\n",
    "        ls = len(nums)\n",
    "        # p[i] = nums[:i]的异或结果\n",
    "        p = nums[::]\n",
    "        for i in range(1, ls):\n",
    "            p[i] ^= p[i-1]\n",
    "        p = [0] + p\n",
    "        \n",
    "        ans = 0\n",
    "        # d[x] = 之前异或结果为x的p数量\n",
    "        d = defaultdict(int)\n",
    "        for x in p:\n",
    "            ans += d[x]\n",
    "            print(x, ans)\n",
    "            d[x] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
